#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
}BTNode;

BTNode * CreatBtree(int A[],int n)
{

    int i;
    BTNode *root,*c,*pa,*p;
    //创建根节点
    root=(BTNode *)malloc(sizeof(BTNode));
    root->data=A[0];
    root->left=root->right=NULL;
    //创建其他节点
    for(i=1;i<n;i++)
    {
        p=(BTNode *)malloc(sizeof(BTNode));
        p->data=A[i];
        p->left=p->right=NULL;
        c=root;

        while(c)
        {
            pa=c;
            if(c->data>p->data)
                c=c->left;
            else
                c=c->right;
        }
        if(pa->data>p->data)
            pa->left=p;
        else
            pa->right=p;

    }
    return root;
}

void FOnder(BTNode *root)
{
    if(root){
        printf("%5d",root->data);
        FOnder(root->left);
        FOnder(root->right);
    }
}

void InOrder(BTNode *root)
{
    if(root)
    {
        InOrder(root->left);
        printf("%5d",root->data);
        InOrder(root->right);
    }
}

void PreOrder(BTNode * root){
    if(root){
        PreOrder(root->left);
        PreOrder(root->right);
        printf("%d",root->data);
    }
}

void printByFloor(BTNode * root,int n){
    BTNode ** s=(BTNode **)malloc(sizeof(BTNode *)*(n+1));
    int front=0,rear=0;
    BTNode * p=root;
    s[++rear]=root;
    while(front-rear){

        if(p->left)
            s[++rear]=p->left;
        if(p->right)
            s[++rear]=p->right;
        printf("%d",p->data);
        p=s[++front+1];
    }
}

void fOrderByStack(BTNode * root,int n){
    BTNode ** s=(BTNode **)malloc(sizeof(BTNode *)*n);
    int top=-1;
    BTNode * p=root;
    s[++top]=p;
    while(top>-1){
        p=s[top--];
        printf("%d",p->data);
        if(p->right)
            s[++top]=p->right;
        if(p->left)
            s[++top]=p->left;
    }
}

void inOrderByStack(BTNode * root,int n){
    BTNode ** s=(BTNode **)malloc(sizeof(BTNode *)*n);
    int top=-1;
    BTNode * p=root;
    s[++top]=p;
    while(top>-1){
        p=s[top--];
        if(p->right)
            s[++top]=p->right;
        if(p->left)
            s[++top]=p->left;
    }
}

int main(void)
{
    int A[9]={6,2,3,7,4,8,5,9,1};
    BTNode *root;
    //创建一颗二叉排序树
    root = CreatBtree(A,9);
    //前序遍历
    FOnder(root);
    //中序遍历
    //InOrder(root);
    //层序遍历
    //printByFloor(root,9);
    //非递归前序
    fOrderByStack(root,9);
 }